#ifndef _LINK_LIST_H_
#define _LINK_LIST_H_

#include <assert.h>

/******************************************************************
 * link list
 ******************************************************************/
template <class t_obj>
struct list_node
{
	t_obj				data;

	list_node<t_obj>	* prev;
	list_node<t_obj>	* next;
};

template <class t_obj>
class link_list
{
public:
	link_list(void);
	~link_list(void);

	int					get_len		( void )						{ return m_len; }

	void				free		( int free_memory = 1 );

	list_node<t_obj> *	append		( list_node<t_obj> * pobj );
	list_node<t_obj> *	prepend		( list_node<t_obj> * pobj );

	void 				remove		( list_node<t_obj> * pobj );

	list_node<t_obj> *	front_push	( list_node<t_obj> * pobj )		{ return prepend(pobj); }
	list_node<t_obj> *	front_pop	( void );

	list_node<t_obj> *	back_push	( list_node<t_obj> * pobj )		{ return append(pobj); }
	list_node<t_obj> *	back_pop	( void );

	list_node<t_obj> *	next		( list_node<t_obj> * pobj );

private:
#ifdef LIST_CLASH_CHECK
	int					addr_clash	( list_node<t_obj> * pobj );
#endif

protected:
	int					m_len;
	list_node<t_obj>	* m_phead;
	list_node<t_obj>	* m_ptail;
};

template <class t_obj>
link_list<t_obj>::link_list(void)
{
	m_phead		= NULL;
	m_ptail		= NULL;
	m_len		= 0;
}

template <class t_obj>
link_list<t_obj>::~link_list(void)
{
	free(0);
}

template <class t_obj>
void link_list<t_obj>::free( int free_memory )
{
	if( free_memory )
	{
		list_node<t_obj> *	p1 = m_phead;
		list_node<t_obj> *	p2;

		while( p1 != NULL )
		{
			p2	= p1;
			p1	= p1->next;

			delete p2;
		}
	}

	m_phead		= NULL;
	m_ptail		= NULL;
	m_len		= 0;
}

template <class t_obj>
list_node<t_obj> * link_list<t_obj>::append( list_node<t_obj> * pobj )
{
	assert( pobj != NULL );

#ifdef LIST_CLASH_CHECK
	if( addr_clash( pobj ) )
	{
		return pobj;
	}
#endif

	pobj->next	= NULL;
	if( m_phead == NULL )
	{
		pobj->prev	= NULL;
		m_phead		= pobj;
	}
	else
	{
		m_ptail->next	= pobj;
		pobj->prev		= m_ptail;
	}
	m_ptail	= pobj;
	m_len++;

	return pobj;
}

template <class t_obj>
list_node<t_obj> * link_list<t_obj>::prepend( list_node<t_obj> * pobj )
{
	assert( pobj != NULL );

#ifdef LIST_CLASH_CHECK
	if( addr_clash( pobj ) )
	{
		return pobj;
	}
#endif

	pobj->prev	= NULL;
	if( m_phead == NULL )
	{
		pobj->next	= NULL;
		m_ptail		= pobj;
	}
	else
	{
		pobj->next		= m_phead;
		m_phead->prev	= pobj;
	}
	m_phead		= pobj;
	m_len++;

	return pobj;
}

template <class t_obj>
void link_list<t_obj>::remove( list_node<t_obj> * pobj )
{
	assert( pobj != NULL );

	if( m_phead == NULL )
		return;

	//
	if( pobj == m_phead )
	{
		m_phead	= m_phead->next;
	}
	if( pobj == m_ptail )
	{
		m_ptail	= m_ptail->prev;
	}

	//
	if( pobj->next != NULL )
	{
		pobj->next->prev	= pobj->prev;
	}
	if( pobj->prev != NULL )
	{
		pobj->prev->next	= pobj->next;
	}
	pobj->next	= NULL;
	pobj->prev	= NULL;

	m_len--;
}

template <class t_obj>
list_node<t_obj> * link_list<t_obj>::front_pop( void )
{
	if( m_phead == NULL )
	{
		return NULL;
	}

	list_node<t_obj>	* p;

	p		= m_phead;
	remove( m_phead );

	return p;
}

template <class t_obj>
list_node<t_obj> * link_list<t_obj>::back_pop( void )
{
	if( m_ptail == NULL )
	{
		return NULL;
	}

	list_node<t_obj>	* p;

	p		= m_ptail;
	remove( m_ptail );

	return p;
}

template <class t_obj>
list_node<t_obj> * link_list<t_obj>::next( list_node<t_obj> * pnode )
{
	return (pnode == NULL) ? m_phead : (pnode->next);
}

#ifdef LIST_CLASH_CHECK
template <class t_obj>
int link_list<t_obj>::addr_clash( list_node<t_obj> * pobj )
{
	list_node<t_obj> *	p = m_phead;

	while( p != NULL )
	{
		if( p == pobj )
		{
			return 1;
		}

		p	= p->next;
	}

	return 0;
}
#endif

#endif
